package com.leetcode_mianshi_150;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

class BSTIterator {


    //方式一    18ms   14
    //List<TreeNode> iteratorBase;
    //int currIndex;
    //int maxSize;
    //
    //public BSTIterator(TreeNode root) {
    //    iteratorBase = inorderTraversal(root);
    //    currIndex = -1;
    //    maxSize = iteratorBase.size();
    //}
    //
    //public int next() {
    //    return iteratorBase.get(++currIndex).val;
    //}
    //
    //public boolean hasNext() {
    //    if (currIndex + 1 >= maxSize) {
    //        return false;
    //    }
    //
    //    return true;
    //}
    //
    //public List<TreeNode> inorderTraversal(TreeNode root) {
    //    ArrayList<TreeNode> res = new ArrayList<>();
    //    if (root == null) {
    //        return res;
    //    }
    //
    //    Stack<TreeNode> stack = new Stack<>();
    //    TreeNode curr = root;
    //
    //    while (!stack.isEmpty() || curr != null) {
    //        if (curr != null) {
    //            stack.push(curr);
    //            curr = curr.left;
    //        } else {
    //            TreeNode node = stack.pop();
    //            res.add(node);
    //
    //            if (node.right != null) {
    //                node = node.right;
    //            }
    //        }
    //    }
    //    return res;
    //}


    //方式二 17 44
    Stack<TreeNode> stack;
    TreeNode curr;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        curr = root;
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        curr = node.right;
        while (curr != null) {
            stack.push(curr);
            curr = curr.right;
        }

        return node.val;
    }

    public boolean hasNext() {
        if (!stack.isEmpty()) {
            return true;
        }

        return false;
    }



}
